#!/usr/bin/env python
# -*- coding: utf-8 -*-

class bubble_sort(object):
    def __init__(self):
         pass

    """
        最优时间复杂度：O(n)  【表示遍历一次发现没有任何可以交换的元素,排序结束,此时需要加一个计数值判断元素之间是否进行了交换】
        最坏时间复杂度：O(n2)
        稳定定：稳定 【连续交换】
    """
    def bubble_sort_1(self, alist):
        """冒泡排序"""
        """外层循环控制走多少次，内层循环控制从头走到尾"""
        n = len(alist)
        for j in range(n-1):   # rang(n)生成[0, 1, ....., n-1]
            for i in range(0, n-1):    # 时间复杂度要看最坏的
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i+1] = alist[i+1], alist[i]
            n -= 1


    def bubble_sort_2(self, alist):
        n = len(alist)
        for j in range(n-1, 0, -1):
            for i in range(j):
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i+1] = alist[i+1], alist[i]


    # 最有时间复杂度
    # 优化：对于有序的序列不进行排序[1,2,3,4,5]   【优化是改进最优时间复杂度, 最坏时间复杂度是不变的】
    def bubble_sort_3(self, alist):
        n = len(alist)
        for j in range(n-1-j):
            count = 0
            for i in range(0, n-1):
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i+1] = alist[i+1], alist[i]
                    count += 1
            if 0 == count:
                break

# 选择和插入算法实际上是把序列分为两部分
class select_insert_sort(object):
    def __init__(self):
        pass
    
    """
        按住头不动,遍历后面无序的序列进行比较，找到最大或最小的插入到头部，移位依次循环
    
        最优时间复杂度：O(n2)
        最坏时间复杂度：O(n2)
        稳定性：不稳定 [26, 12, 17, 26, 13, 9]第一个26会跟最后的9作交换【跳跃交换】
    """
    def select_sort_1(self, alist):
        n = len(alist)
        for i in range(n-1):
            pos = i
            for j in range(i + 1, n):
                if alist[pos] < alist[j]:
                    pos = j
            alist[i], alist[pos] = alist[pos], alist[i]


    """
        插入排序是一种简单直观的排序算法.他的工作原理是通过构建有序序列, 对于未排序数据, 在已经排序序列中从后往前扫描,找到相应位置并插入.
        插入排序在实现上, 在从后向前扫描过程中,需要反复吧已经排序元素逐步向后挪位, 为最新元素提供插入空间


        最优时间复杂度：O(n)【即数组是有序的，只进行n次外层，而内层循环都是执行一次】
        最坏时间复杂度：O(n2)【此时不加else条件判断，执行次数为1，2，3......n-1】
        稳定性：稳定 【连续交换】
    """
    def insert_sort_2(self, alist):
        n = len(alist)
        for i in range(1, n):
            for j in list(range(i, 0, -1)):
                if alist[j - 1] > alist[j]:
                    alist[j - 1], alist[j] = alist[j], alist[j - 1]
                else:
                    break

             



if __name__ == "__main__":
    li = [34, 5, 6, 54, 7, 64, 59, 38, 42]
    # bubble_sort().bubble_sort_1(li)
    #select_insert_sort().select_sort_1(li)
    select_insert_sort().insert_sort_1(li)
    print li # , new[1], id(new[1])
